package main

import (
	"fmt"
	"sync"
)

// 二叉树的实现——链表

type TreeNode struct {
	Data string 		// 储存数据
	Left *TreeNode   	// 左子节点
	Right *TreeNode 	// 右子节点
}

// PreOrderTraversal 二叉树前序遍历：根——左——右
func PreOrderTraversal(tree *TreeNode) {
	// 递归结束条件
	if tree == nil {
		return
	}
	fmt.Print(tree.Data, " ")
	PreOrderTraversal(tree.Left)
	PreOrderTraversal(tree.Right)
}

// MidOrderTraversal 中序遍历: 左——根——右
func MidOrderTraversal(tree *TreeNode) {
	// 递归结束条件
	if tree == nil {
		return
	}
	MidOrderTraversal(tree.Left)
	fmt.Print(tree.Data, " ")
	MidOrderTraversal(tree.Right)
}

// PostOrderTraversal 后序遍历: 左——右——根
func PostOrderTraversal(tree *TreeNode) {
	// 递归终止条件
	if tree == nil {
		return
	}
	PostOrderTraversal(tree.Left)
	PostOrderTraversal(tree.Right)
	fmt.Print(tree.Data, " ")
}

// LinkNode 链式队列的节点定义
type LinkNode struct {
	Next *LinkNode
	Value *TreeNode
}

// LinkQueue 链式队列定义
type LinkQueue struct {
	root *LinkNode  // 队列头节点
	size int		// 队列的元素数量
	lock sync.Mutex // 为了并发安全使用的互斥锁
}

// Add 入队操作：尾插
func (queue *LinkQueue) Add(v *TreeNode) {
	// 加锁操作
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 如果栈顶为空，那么直接增加节点
	if queue.root == nil {
		queue.root = new(LinkNode)
		queue.root.Value = v
	} else {
		// 否则新元素插入队列的尾部

		newNode := new(LinkNode)
		newNode.Value = v

		// 遍历到队列尾部
		nowNode := queue.root
		for nowNode.Next != nil {
			nowNode = nowNode.Next
		}

		// 新节点放在队列尾部
		nowNode.Next = newNode
	}
	// 队列中元素数量 + 1
	queue.size = queue.size + 1
}

// Remove 出队操作: 头删
func (queue *LinkQueue) Remove() *TreeNode {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 如果队列为空
	if queue.size == 0 {
		panic("over limit")
	}

	// 头部元素出队
	topNode := queue.root
	v := topNode.Value

	queue.root = topNode.Next

	// 队中元素数量 - 1
	queue.size = queue.size - 1

	return v
}

// Size 求队列中的元素数量
func (queue *LinkQueue) Size() int {
	return queue.size
}

// LayerOrderTraversal 二叉树层序遍历——BFS
func LayerOrderTraversal(treeNode *TreeNode) {
	if treeNode == nil {
		return
	}
	// 建立队列
	queue := new(LinkQueue)
	// 根节点入队
	queue.Add(treeNode)

	for queue.size > 0 {
		element := queue.Remove()

		// 打印节点值
		fmt.Print(element.Data, " ")

		// 处理左子树
		if element.Left != nil {
			queue.Add(element.Left)
		}

		// 处理右子树
		if element.Right != nil {
			queue.Add(element.Right)
		}
	}
}


func main() {

	t := &TreeNode{Data: "A"}
	t.Left = &TreeNode{Data: "B"}
	t.Right = &TreeNode{Data: "C"}
	t.Left.Left = &TreeNode{Data: "D"}
	t.Left.Right = &TreeNode{Data: "E"}
	t.Right.Left = &TreeNode{Data: "F"}
	fmt.Println("\n层次排序")
	LayerOrderTraversal(t)

}




















